home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1997 January: Mac OS SDK / Dev.CD Jan 97 SDK2.toast / Development Kits (Disc 2) / OpenDoc / OpenDoc Development / Debugging Support / OpenDoc™ Source Code / Memory / BestFitH.h < prev    next >
Encoding:
C/C++ Source or Header  |  1996-08-28  |  23.8 KB  |  725 lines  |  [TEXT/MPS ]
  1. /*
  2.     File:        BestFitH.h
  3.  
  4.     Contains:    BestFitHeap class interface
  5.  
  6.     Owned by:    Michael Burbidge
  7.     Owned by:    Jens Alfke
  8.  
  9.     Copyright:    © 1993 - 1995 by Apple Computer, Inc., all rights reserved.
  10.  
  11.     Change History (most recent first):
  12.     
  13.         <10>      5/4/95    jpa        Support for finding largest free block
  14.                                     [1235657] and validating memory ranges
  15.                                     [1246077]
  16.          <9>     1/25/95    jpa        Removed five-$ comments [1210981]
  17.          <8>    10/24/94    jpa        Constness [1194286]
  18.          <7>     9/29/94    RA        1189812: Mods for 68K build.
  19.          <6>     9/14/94    jpa        Eliminated dependencies on rest of OpenDoc.
  20.                                     Added support for getting the heap of a
  21.                                     block by stuffing heap ptr in busy block
  22.                                     header. [1186692]
  23.          <5>     8/17/94    jpa        (Oops, deleted obsolete "in progress" msg)
  24.          <4>     8/17/94    jpa        Implemented huge-block support [1179565],
  25.                                     segment disposal [1181509] and the
  26.                                     SOM-block flag [1181510].
  27.          <3>      8/8/94    jpa        Added fHugeBlockSize -- not used yet
  28.                                     [1179565]
  29.          <2>     6/10/94    MB        Make it build
  30.          <1>      6/9/94    MB        first checked in
  31.          <4>     5/27/94    MB        #1162181: Fixed MMM integration bug
  32.          <2>      5/9/94    MB        #1162181: Changes necessary to install MMM.
  33.          <1>     4/29/94    MB        first checked in
  34.     To Do:
  35.     In Progress:
  36. */
  37.  
  38. #ifndef _BESTFITH_
  39. #define _BESTFITH_
  40.  
  41. #ifndef _MEMORYHE_
  42. #include "MemoryHe.h"
  43. #endif
  44.  
  45.  
  46. //========================================================================================
  47. // Forward class declarations
  48. //========================================================================================
  49.  
  50. class PrivBestFitBlock;
  51. class BestFitHeap;
  52.  
  53.  
  54. //========================================================================================
  55. // STRUCT PrivBestFitBlockFreeListLinks
  56. //
  57. // The following fields are only present in free blocks. They are used to link the free
  58. // block into the free block tree. The address of a free block is also stored at the end
  59. // of the block and must be accounted for in the minimum block size.
  60. //========================================================================================
  61.  
  62. struct PrivBestFitBlockFreeListLinks
  63. {
  64.     PrivBestFitBlock* fParent;
  65.     PrivBestFitBlock* fLeft;
  66.     PrivBestFitBlock* fRight;
  67. };
  68.  
  69.  
  70. //========================================================================================
  71. // STRUCT PrivBestFitBlockHeader
  72. //========================================================================================
  73.  
  74. // The fBits field of PrivBestFitBlockHeader contains five fields. The following masks are
  75. // used to get and set the fields. The block type field is used to distinguish best fit
  76. // blocks from chunky blocks and must be the first four bits of the last byte in fBits.
  77.  
  78. #ifdef MM_LITTLE_ENDIAN
  79.     // Bytes are in reverse order in a long.
  80.     
  81.     const unsigned long BestFitBlockHeader_kSizeMask = 0x00FFFFFF;
  82.     const unsigned long BestFitBlockHeader_kSizeShift = 0;
  83.     
  84.     const unsigned long BestFitBlockHeader_kBlockTypeMask = 0xC0000000;
  85.     const unsigned long BestFitBlockHeader_kBlockTypeShift = 30;
  86.     
  87.     const unsigned long BestFitBlockHeader_kIsObjectMask = 0x20000000;    //jpa
  88.     const unsigned long BestFitBlockHeader_kIsObjectShift = 29;
  89.     
  90.     const unsigned long BestFitBlockHeader_kFirstBlockMask = 0x10000000;    //jpa
  91.     const unsigned long BestFitBlockHeader_kFirstBlockShift = 28;
  92.     
  93.     const unsigned long BestFitBlockHeader_kBusyMask = 0x08000000;
  94.     const unsigned long BestFitBlockHeader_kBusyShift = 27;
  95.     
  96.     const unsigned long BestFitBlockHeader_kPreviousBusyMask = 0x04000000;
  97.     const unsigned long BestFitBlockHeader_kPreviousBusyShift = 26;
  98.     
  99.     const unsigned long BestFitBlockHeader_kMagicNumberMask = 0x03000000;
  100.     const unsigned long BestFitBlockHeader_kMagicNumberShift = 24;
  101. #else
  102.     const unsigned long BestFitBlockHeader_kSizeMask = 0xFFFFFF00;
  103.     const unsigned long BestFitBlockHeader_kSizeShift = 8;
  104.     
  105.     const unsigned long BestFitBlockHeader_kBlockTypeMask = 0x000000C0;
  106.     const unsigned long BestFitBlockHeader_kBlockTypeShift = 6;
  107.     
  108.     const unsigned long BestFitBlockHeader_kIsObjectMask = 0x00000020;    //jpa
  109.     const unsigned long BestFitBlockHeader_kIsObjectShift = 5;
  110.     
  111.     const unsigned long BestFitBlockHeader_kFirstBlockMask = 0x00000010;    //jpa
  112.     const unsigned long BestFitBlockHeader_kFirstBlockShift = 4;
  113.     
  114.     const unsigned long BestFitBlockHeader_kBusyMask = 0x00000008;
  115.     const unsigned long BestFitBlockHeader_kBusyShift = 3;
  116.     
  117.     const unsigned long BestFitBlockHeader_kPreviousBusyMask = 0x00000004;
  118.     const unsigned long BestFitBlockHeader_kPreviousBusyShift = 2;
  119.     
  120.     const unsigned long BestFitBlockHeader_kMagicNumberMask = 0x00000003;
  121.     const unsigned long BestFitBlockHeader_kMagicNumberShift = 0;
  122. #endif
  123.  
  124. struct PrivBestFitBlockHeader
  125. {
  126.     unsigned long fBits;
  127.     union{
  128.         BestFitHeap* fHeap;                            //jpa: Added ptr back to heap 9/10/94
  129.         PrivBestFitBlockFreeListLinks fFreeLinks;
  130.     };
  131. };
  132.  
  133.  
  134. //========================================================================================
  135. // CLASS PrivBestFitBlock
  136. //========================================================================================
  137.  
  138. #ifdef BUILD_WIN16
  139. const ODBlockSize BestFitBlock_kMaxBlockSize = 60L * 1024L;
  140.     // Block size limited by 64K limit of far pointers. Allow 4K for overhead in the
  141.     // various layers.
  142. #else
  143. const ODBlockSize BestFitBlock_kMaxBlockSize = 0x00FFFFFF;
  144. #endif
  145.  
  146. class PrivBestFitBlock
  147. {
  148. public:
  149.  
  150.     enum
  151.     {
  152.         kBusyOverhead = sizeof(unsigned long) + sizeof(BestFitHeap*),    //jpa added heap overhead 9/10/94 
  153.         kMinBlockSize = sizeof(PrivBestFitBlockHeader) + sizeof(void *), 
  154.         kBlockTypeId = MemoryHeap::kBlockTypeId + 1, 
  155.         kMagicNumber = 0x3
  156.     };
  157.  
  158.  
  159.     Boolean operator>(const PrivBestFitBlock& blk) const;
  160.     Boolean operator<(const PrivBestFitBlock& blk) const;
  161.     Boolean operator>=(const PrivBestFitBlock& blk) const;
  162.     Boolean operator<=(const PrivBestFitBlock& blk) const;
  163.     Boolean operator==(const PrivBestFitBlock& blk) const;
  164.     Boolean operator!=(const PrivBestFitBlock& blk) const;
  165.     PrivBestFitBlock& operator=(const PrivBestFitBlock& blk);
  166.  
  167.     inline void operator delete(void *) { };
  168.     void* operator new(SIZE_T, void* ptr);
  169.     void* operator new(SIZE_T);
  170.  
  171.     PrivBestFitBlock(int busy,
  172.                      int prevBusy,
  173.                      long size);
  174.     PrivBestFitBlock(const PrivBestFitBlock& otherBlock);
  175.  
  176.     BestFitHeap*        GetHeap() const;                //jpa 9/10/94
  177.     Boolean                GetBusy() const;
  178.     Boolean                GetIsFirst() const;                //jpa
  179.     Boolean                GetIsObject() const;            //jpa
  180.     PrivBestFitBlock*    GetLeft() const;
  181.     unsigned int        GetMagicNumber() const;
  182.     PrivBestFitBlock*    GetNext() const;
  183.     PrivBestFitBlock*    GetParent() const;
  184.     Boolean                GetPreviousBusy() const;
  185.     PrivBestFitBlock*    GetRight() const;
  186.     ODBlockSize            GetSize() const;
  187.     unsigned short        GetBlockType() const;
  188.  
  189.     void SetHeap(BestFitHeap*);                            //jpa 9/10/94
  190.     void SetBusy(Boolean busy);
  191.     void SetIsFirst(Boolean first);                        //jpa
  192.     void SetIsObject(Boolean isObj);                    //jpa
  193.     void SetLeft(PrivBestFitBlock* left);
  194.     void SetNext(PrivBestFitBlock* fNext);
  195.     void SetParent(PrivBestFitBlock* parent);
  196.     void SetPrevBusy(Boolean busy);
  197.     void SetRight(PrivBestFitBlock* right);
  198.     void SetSize(ODBlockSize size);
  199.     void SetBlockType(unsigned long blockType);
  200.     void SetMagicNumber(unsigned long magicNumber);
  201.  
  202.     void StuffAddressAtEnd();
  203.  
  204. protected:
  205.  
  206. private:
  207.     PrivBestFitBlockHeader fHeader;
  208. };
  209.  
  210. //----------------------------------------------------------------------------------------
  211. // PrivBestFitBlock::operator delete
  212. //----------------------------------------------------------------------------------------
  213. /*
  214. inline void PrivBestFitBlock::operator delete(void*)
  215. {
  216. }
  217. */
  218. //----------------------------------------------------------------------------------------
  219. // PrivBestFitBlock::operator new
  220. //----------------------------------------------------------------------------------------
  221.  
  222. inline void* PrivBestFitBlock::operator new(SIZE_T, void* ptr)
  223. {
  224.     return ptr;
  225. }
  226.  
  227. //----------------------------------------------------------------------------------------
  228. // PrivBestFitBlock::operator new
  229. //----------------------------------------------------------------------------------------
  230.  
  231. inline void* PrivBestFitBlock::operator new(SIZE_T)
  232. {
  233.     return NULL;
  234. }
  235.  
  236. //----------------------------------------------------------------------------------------
  237. // PrivBestFitBlock::operator>=
  238. //----------------------------------------------------------------------------------------
  239.  
  240. inline Boolean PrivBestFitBlock::operator>=(const PrivBestFitBlock& blk) const
  241. {
  242.     return *this > blk || *this == blk;
  243. }
  244.  
  245. //----------------------------------------------------------------------------------------
  246. // PrivBestFitBlock::operator<=
  247. //----------------------------------------------------------------------------------------
  248.  
  249. inline Boolean PrivBestFitBlock::operator<=(const PrivBestFitBlock& blk) const
  250. {
  251.     return *this < blk || *this == blk;
  252. }
  253.  
  254. //----------------------------------------------------------------------------------------
  255. // PrivBestFitBlock::operator!=
  256. //----------------------------------------------------------------------------------------
  257.  
  258. inline Boolean PrivBestFitBlock::operator!=(const PrivBestFitBlock& blk) const
  259. {
  260.     return !(*this == blk);
  261. }
  262.  
  263. //----------------------------------------------------------------------------------------
  264. // PrivBestFitBlock::operator=
  265. //----------------------------------------------------------------------------------------
  266.  
  267. inline PrivBestFitBlock& PrivBestFitBlock::operator=(const PrivBestFitBlock& blk)
  268. {
  269.     fHeader = blk.fHeader;
  270.     return (*this);
  271. }
  272.  
  273. //----------------------------------------------------------------------------------------
  274. // PrivBestFitBlock::PrivBestFitBlock
  275. //----------------------------------------------------------------------------------------
  276.  
  277. inline PrivBestFitBlock::PrivBestFitBlock(const PrivBestFitBlock& blk) :
  278.     fHeader(blk.fHeader)
  279. {
  280. }
  281.  
  282. //----------------------------------------------------------------------------------------
  283. // PrivBestFitBlock::GetBusy
  284. //----------------------------------------------------------------------------------------
  285.  
  286. inline Boolean PrivBestFitBlock::GetBusy() const
  287. {
  288.     return (fHeader.fBits & BestFitBlockHeader_kBusyMask) != 0 ? true : false;
  289. }
  290.  
  291. //----------------------------------------------------------------------------------------
  292. // PrivBestFitBlock::GetIsFirst
  293. //----------------------------------------------------------------------------------------
  294.  
  295. inline Boolean PrivBestFitBlock::GetIsFirst() const
  296. {
  297.     return (fHeader.fBits & BestFitBlockHeader_kFirstBlockMask) != 0 ? true : false;
  298. }
  299.  
  300. //----------------------------------------------------------------------------------------
  301. // PrivBestFitBlock::GetIsObject
  302. //----------------------------------------------------------------------------------------
  303.  
  304. inline Boolean PrivBestFitBlock::GetIsObject() const
  305. {
  306.     return (fHeader.fBits & BestFitBlockHeader_kIsObjectMask) != 0 ? true : false;
  307. }
  308.  
  309. //----------------------------------------------------------------------------------------
  310. // PrivBestFitBlock::GetLeft
  311. //----------------------------------------------------------------------------------------
  312.  
  313. inline PrivBestFitBlock* PrivBestFitBlock::GetLeft() const
  314. {
  315.     return fHeader.fFreeLinks.fLeft;
  316. }
  317.  
  318. //----------------------------------------------------------------------------------------
  319. // PrivBestFitBlock::GetMagicNumber
  320. //----------------------------------------------------------------------------------------
  321.  
  322. inline unsigned int PrivBestFitBlock::GetMagicNumber() const
  323. {
  324.     return (fHeader.fBits & BestFitBlockHeader_kMagicNumberMask)
  325.                 >> BestFitBlockHeader_kMagicNumberShift;
  326. }
  327.  
  328. //----------------------------------------------------------------------------------------
  329. // PrivBestFitBlock::GetNext
  330. //----------------------------------------------------------------------------------------
  331.  
  332. inline PrivBestFitBlock* PrivBestFitBlock::GetNext() const
  333. {
  334.     return fHeader.fFreeLinks.fParent;
  335. }
  336.  
  337. //----------------------------------------------------------------------------------------
  338. // PrivBestFitBlock::GetParent
  339. //----------------------------------------------------------------------------------------
  340.  
  341. inline PrivBestFitBlock* PrivBestFitBlock::GetParent() const
  342. {
  343.     return fHeader.fFreeLinks.fParent;
  344. }
  345.  
  346. //----------------------------------------------------------------------------------------
  347. // PrivBestFitBlock::GetPreviousBusy
  348. //----------------------------------------------------------------------------------------
  349.  
  350. inline Boolean PrivBestFitBlock::GetPreviousBusy() const
  351. {
  352.     return (fHeader.fBits & BestFitBlockHeader_kPreviousBusyMask) != 0 ? true : false;
  353. }
  354.  
  355. //----------------------------------------------------------------------------------------
  356. // PrivBestFitBlock::GetRight
  357. //----------------------------------------------------------------------------------------
  358.  
  359. inline PrivBestFitBlock* PrivBestFitBlock::GetRight() const
  360. {
  361.     return fHeader.fFreeLinks.fRight;
  362. }
  363.  
  364. //----------------------------------------------------------------------------------------
  365. // PrivBestFitBlock::GetSize
  366. //----------------------------------------------------------------------------------------
  367.  
  368. inline ODBlockSize PrivBestFitBlock::GetSize() const
  369. {
  370.     return (fHeader.fBits & BestFitBlockHeader_kSizeMask)
  371.                 >> BestFitBlockHeader_kSizeShift;
  372. }
  373.  
  374. //----------------------------------------------------------------------------------------
  375. // PrivBestFitBlock::GetBlockType
  376. //----------------------------------------------------------------------------------------
  377.  
  378. inline unsigned short PrivBestFitBlock::GetBlockType() const
  379. {
  380.     return (fHeader.fBits & BestFitBlockHeader_kBlockTypeMask)
  381.                 >> BestFitBlockHeader_kBlockTypeShift;
  382. }
  383.  
  384. //----------------------------------------------------------------------------------------
  385. // PrivBestFitBlock::SetBusy
  386. //----------------------------------------------------------------------------------------
  387.  
  388. inline void PrivBestFitBlock::SetBusy(Boolean busy)
  389. {
  390.     if (busy)
  391.         fHeader.fBits |=  BestFitBlockHeader_kBusyMask;
  392.     else
  393.         fHeader.fBits &= ~BestFitBlockHeader_kBusyMask;
  394. }
  395.  
  396. //----------------------------------------------------------------------------------------
  397. // PrivBestFitBlock::SetIsFirst
  398. //----------------------------------------------------------------------------------------
  399.  
  400. inline void PrivBestFitBlock::SetIsFirst(Boolean first)
  401. {
  402.     if (first)
  403.         fHeader.fBits |=  BestFitBlockHeader_kFirstBlockMask;
  404.     else
  405.         fHeader.fBits &= ~BestFitBlockHeader_kFirstBlockMask;
  406. }
  407.  
  408. //----------------------------------------------------------------------------------------
  409. // PrivBestFitBlock::SetIsObject
  410. //----------------------------------------------------------------------------------------
  411.  
  412. inline void PrivBestFitBlock::SetIsObject(Boolean isObj)
  413. {
  414.     if (isObj)
  415.         fHeader.fBits |=  BestFitBlockHeader_kIsObjectMask;
  416.     else
  417.         fHeader.fBits &= ~BestFitBlockHeader_kIsObjectMask;
  418. }
  419.  
  420. //----------------------------------------------------------------------------------------
  421. // PrivBestFitBlock::SetLeft
  422. //----------------------------------------------------------------------------------------
  423.  
  424. inline void PrivBestFitBlock::SetLeft(PrivBestFitBlock* left)
  425. {
  426.     fHeader.fFreeLinks.fLeft = left;
  427. }
  428.  
  429. //----------------------------------------------------------------------------------------
  430. // PrivBestFitBlock::SetNext
  431. //----------------------------------------------------------------------------------------
  432.  
  433. inline void PrivBestFitBlock::SetNext(PrivBestFitBlock* fNext)
  434. {
  435.     // The fParent field is used both for a parent and a next pointer on different
  436.     // occasions.
  437.     
  438.     fHeader.fFreeLinks.fParent = fNext;
  439. }
  440.  
  441. //----------------------------------------------------------------------------------------
  442. // PrivBestFitBlock::SetParent
  443. //----------------------------------------------------------------------------------------
  444.  
  445. inline void PrivBestFitBlock::SetParent(PrivBestFitBlock* parent)
  446. {
  447.     fHeader.fFreeLinks.fParent = parent;
  448. }
  449.  
  450. //----------------------------------------------------------------------------------------
  451. // PrivBestFitBlock::SetPrevBusy
  452. //----------------------------------------------------------------------------------------
  453.  
  454. inline void PrivBestFitBlock::SetPrevBusy(Boolean busy)
  455. {
  456.     if (busy)
  457.         fHeader.fBits |= BestFitBlockHeader_kPreviousBusyMask;
  458.     else
  459.         fHeader.fBits &= ~BestFitBlockHeader_kPreviousBusyMask;
  460. }
  461.  
  462. //----------------------------------------------------------------------------------------
  463. // PrivBestFitBlock::SetRight
  464. //----------------------------------------------------------------------------------------
  465.  
  466. inline void PrivBestFitBlock::SetRight(PrivBestFitBlock* right)
  467. {
  468.     fHeader.fFreeLinks.fRight = right;
  469. }
  470.  
  471. //----------------------------------------------------------------------------------------
  472. // PrivBestFitBlock::SetSize
  473. //----------------------------------------------------------------------------------------
  474.  
  475. inline void PrivBestFitBlock::SetSize(ODBlockSize size)
  476. {
  477.     fHeader.fBits &= ~BestFitBlockHeader_kSizeMask;
  478.     fHeader.fBits |= (size << BestFitBlockHeader_kSizeShift)
  479.                         & BestFitBlockHeader_kSizeMask;
  480. }
  481.  
  482. //----------------------------------------------------------------------------------------
  483. // PrivBestFitBlock::SetBlockType
  484. //----------------------------------------------------------------------------------------
  485.  
  486. inline void PrivBestFitBlock::SetBlockType(unsigned long blockType)
  487. {
  488.     fHeader.fBits &= ~BestFitBlockHeader_kBlockTypeMask;
  489.     fHeader.fBits |= (blockType << BestFitBlockHeader_kBlockTypeShift)
  490.                         & BestFitBlockHeader_kBlockTypeMask;
  491. }
  492.  
  493. //----------------------------------------------------------------------------------------
  494. // PrivBestFitBlock::SetMagicNumber
  495. //----------------------------------------------------------------------------------------
  496.  
  497. inline void PrivBestFitBlock::SetMagicNumber(unsigned long magicNumber)
  498. {
  499.     fHeader.fBits &= ~BestFitBlockHeader_kMagicNumberMask;
  500.     fHeader.fBits |= (magicNumber << BestFitBlockHeader_kMagicNumberShift)
  501.                         & BestFitBlockHeader_kMagicNumberMask;
  502. }
  503.  
  504. //----------------------------------------------------------------------------------------
  505. // PrivBestFitBlock::GetHeap
  506. //----------------------------------------------------------------------------------------
  507. inline BestFitHeap* PrivBestFitBlock::GetHeap() const
  508. {
  509.     MM_ASSERT(this->GetBusy());
  510.     return fHeader.fHeap;
  511. }
  512.  
  513. //----------------------------------------------------------------------------------------
  514. // PrivBestFitBlock::SetHeap
  515. //----------------------------------------------------------------------------------------
  516. inline void PrivBestFitBlock::SetHeap(BestFitHeap *heap)
  517. {
  518.     MM_ASSERT(this->GetBusy());
  519.     fHeader.fHeap = heap;
  520. }
  521.  
  522. //----------------------------------------------------------------------------------------
  523. // PrivBestFitBlock::PrivBestFitBlock
  524. //----------------------------------------------------------------------------------------
  525.  
  526. inline PrivBestFitBlock::PrivBestFitBlock(int busy,
  527.                                           int previousBusy,
  528.                                           long size)
  529. {
  530.     SetParent(NULL);
  531.     SetRight(NULL);
  532.     SetLeft(NULL);
  533.     
  534.     // ***** Setting these 4 bits can be greatly optimized -- slam a constant into fFlags
  535.     SetIsFirst(false);                                        //jpa
  536.     SetIsObject(false);                                        //jpa
  537.     SetBlockType(kBlockTypeId);
  538.     SetMagicNumber(kMagicNumber);
  539.  
  540.     SetBusy(busy);
  541.     SetPrevBusy(previousBusy);
  542.     SetSize(size);
  543.  
  544.     if (!busy)
  545.         this->StuffAddressAtEnd();
  546. }
  547.  
  548.  
  549. //========================================================================================
  550. // CLASS PrivBestFitSegment
  551. //
  552. //        The BestFitHeap allocates memory from the system in segments. The segments are
  553. //        linked together in a list so that When the heap is destroyed all segments can be
  554. //        freed.
  555. //
  556. //========================================================================================
  557.  
  558. class PrivBestFitSegment
  559. {
  560. public:
  561.  
  562.     friend BestFitHeap;
  563.  
  564.     enum
  565.     {
  566.         kSegmentPrefixSize = 12,
  567.         kSegmentSuffixSize = 4,
  568.         kSegmentOverhead = kSegmentPrefixSize + kSegmentSuffixSize
  569.     };
  570.  
  571.     Boolean AddressInSegment(const void* ptr);
  572.     Boolean CheckSegment( HeapWalkProc, void *refCon, ODBlockSize blockHeaderSize );
  573.  
  574. #if MM_DEBUG
  575.     MMBoolean FindBlockContaining( const void *start, const void *end,
  576.                         const void* &blockStart, const void* &blockEnd ) const;
  577. #endif
  578.  
  579. private:
  580.     void *fSegmentSpace;
  581.     unsigned long fSegmentSize;
  582.     PrivBestFitSegment *fNextSegment;
  583.     
  584.     PrivBestFitSegment(const PrivBestFitSegment& blk);
  585.     PrivBestFitSegment& operator=(const PrivBestFitSegment& blk);
  586.         // This class shouldn't be copied.
  587. };
  588.  
  589. //----------------------------------------------------------------------------------------
  590. // INLINES PrivBestFitSegment
  591. //----------------------------------------------------------------------------------------
  592.  
  593. inline Boolean PrivBestFitSegment::AddressInSegment(const void* ptr)
  594. {
  595.     return ptr >= fSegmentSpace &&
  596.             ptr <= (void*) ((ODBytePtr) fSegmentSpace + fSegmentSize);
  597. }
  598.  
  599.  
  600. //========================================================================================
  601. // CLASS PrivFreeBlockTree
  602. //
  603. //        Binary tree for storing free blocks. Dependent on the structure and
  604. //        implementation of PrivBestFitBlock.
  605. //
  606. //========================================================================================
  607.  
  608. class PrivFreeBlockTree
  609. {
  610. public:
  611.     PrivFreeBlockTree();
  612.     PrivFreeBlockTree(const PrivFreeBlockTree& blk);
  613.  
  614.     PrivFreeBlockTree& operator=(const PrivFreeBlockTree& blk);
  615.  
  616.     void AddBlock(PrivBestFitBlock* blk);
  617.     void TreeInfo(unsigned long& bytesFree,
  618.                   unsigned long& numberOfNodes) const;
  619.     void RemoveBlock(PrivBestFitBlock* blk);
  620.     PrivBestFitBlock* SearchForBlock(ODBlockSize size,
  621.                                      void* blk,
  622.                                      PrivBestFitBlock** insertLeaf = NULL);
  623.     const PrivBestFitBlock* FindLargestBlock( ) const;
  624.  
  625. #if MM_DEBUG
  626.     void CheckTree() const;
  627.     void PrintTree() const;
  628. #endif
  629.  
  630. protected:
  631.     PrivBestFitBlock* GetSuccessorBlk(PrivBestFitBlock* blk);
  632.     void TreeInfoHelper(PrivBestFitBlock* blk,
  633.                         unsigned long& bytesFree,
  634.                         unsigned long& numberOfNodes) const;
  635.  
  636. #if MM_DEBUG
  637.     void CheckTreeHelper(PrivBestFitBlock* blk) const;
  638.     void PrintTreeHelper(PrivBestFitBlock* blk,
  639.                          int level = 0) const;
  640. #endif
  641.  
  642. private:
  643.     PrivBestFitBlock fRoot;
  644.  
  645. };
  646.  
  647.  
  648. //========================================================================================
  649. // CLASS BestFitHeap
  650. //
  651. //        Memory allocation heap using the best fit allocation strategy.
  652. //
  653. //========================================================================================
  654.  
  655. class BestFitHeap : public MemoryHeap
  656. {
  657. public:
  658.  
  659.     virtual unsigned long BytesFree() const;
  660.     virtual unsigned long HeapSize() const;
  661.  
  662.     BestFitHeap(unsigned long sizeInitial,
  663.                   unsigned long sizeIncrement = 0,
  664.                   unsigned long hugeBlockSize = 0,        // "0" means sizeIncrement/2
  665.                   MMHeapLocation = kMMTempMemory);
  666.     virtual ~BestFitHeap();
  667.  
  668.     void IBestFitHeap();
  669.     void ExpandHeap(unsigned long sizeInitial, unsigned long sizeIncrement);
  670.     
  671.     long GetSizeIncrement( )    {return fSizeIncrement;}
  672.     long GetHugeBlockSize( )    {return fSizeIncrement;}
  673.     
  674. #if MM_DEBUG
  675.     virtual void Check( HeapWalkProc proc =NULL, void *refCon =NULL ) const;
  676.     virtual Boolean IsMyBlock(const void* blk) const;
  677.     virtual void Print(char* msg = "") const;
  678. #endif
  679.  
  680. protected:
  681.  
  682.     void AddToFreeBlocks(PrivBestFitBlock* blk);
  683.     PrivBestFitBlock* Coalesce(PrivBestFitBlock* blk);
  684.     PrivBestFitBlock* CreateNewSegment(unsigned long size);        //returns free block --jpa
  685.     void DeleteSegment( PrivBestFitSegment *seg );
  686.     void DeleteSegments();
  687.     void GrowHeap(unsigned long sizeIncrement);
  688.     void RemoveFromFreeBlocks(PrivBestFitBlock* blk);
  689.     PrivBestFitBlock* SearchFreeBlocks(ODBlockSize size);
  690.  
  691.     virtual void* DoAllocate(ODBlockSize size, ODBlockSize& allocatedSize);
  692.     virtual ODBlockSize DoBlockSize(const void* block) const;
  693.     virtual void DoFree(void*);
  694.     virtual void DoReset();
  695.     virtual unsigned long DoLargestFreeBlock() const;
  696.  
  697.     virtual void DoSetBlockIsObject( void* ptr, Boolean isObject );
  698.     
  699.     virtual Boolean DoBlockIsObject( const void* ptr ) const;
  700.  
  701.     virtual MemoryHeap* DoGetBlockHeap( const void* ) const;
  702.  
  703. #if MM_DEBUG
  704.     virtual void CompilerCheck();
  705.     virtual Boolean DoIsValidBlock(const void* blk) const;
  706.     MMBoolean DoFindBlockContaining( const void *start, const void *end,
  707.                         const void* &blockStart, const void* &blockEnd ) const;
  708. #endif
  709.  
  710. private:
  711.     PrivBestFitSegment* fSegments;
  712.     unsigned long fSizeIncrement;
  713.     unsigned long fSizeInitial;
  714.     unsigned long fHugeBlockSize;            //jpa
  715.     PrivFreeBlockTree fFreeTree;
  716.     
  717.     enum{ kMaxHugeBlockSize = 65535L };
  718.     
  719.     BestFitHeap(const BestFitHeap& blk);
  720.     BestFitHeap& operator=(const BestFitHeap& blk);
  721.         // This class shouldn't be copied.
  722. };
  723.  
  724. #endif
  725.